package tree;


import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

/**
 * @author linzou@linkdoc.com
 * @ClassName: BST
 * @Description:
 * @date 2018/12/28 8:42 AM
 */
public class BST<E extends Comparable<E>> {


    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }


    private Node root;
    private int size;

    public BST() {
        this.root = null;
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 向二分搜索树种添加一个新的元素e
     *
     * @param e
     */
    public void add(E e) {

//        if(Objects.isNull(this.root)){
//            this.root = new Node(e);
//            this.size ++ ;
//        }else{
//
//        }

        this.root = add(this.root, e);


    }

    /**
     * 向以node为根的二分搜索树中插入元素E，递归算法
     * 返回新插入节点后二分搜索树的根
     *
     * @param node
     * @param e
     * @return
     */
    private Node add(Node node, E e) {

//        if(e.equals(node.e)){
//            return;
//        }else if(e.compareTo(node.e) < 0 && Objects.isNull(node.left)){
//            node.left = new Node(e);
//            size ++;
//            return;
//        }else if(e.compareTo(node.e) > 0 && Objects.isNull(node.right)){
//            node.right = new Node(e);
//            size ++;
//            return;
//        }

        if (Objects.isNull(node)) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }

        return node;
    }

    /**
     * 是否包含某元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return this.contains(this.root, e);
    }

    public boolean contains(Node node, E e) {

        if (Objects.isNull(e)) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return this.contains(node.left, e);
        } else {
            return this.contains(node.right, e);
        }

    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        this.preOrder(this.root);
    }

    private void preOrder(Node node) {

//        if(Objects.isNull(node)){
//            return;
//        }

        if (Objects.nonNull(node)) {
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }

    }

    /**
     * 二分搜索树非递归前序遍历
     * @Title: preOrderNR
     * @Description:
     * @param
     * @return void
     * @modify
     * @throws
     * @author linzou@linkdoc.com
     * @date 2019/1/14 9:46 PM
     */
    public void preOrderNR(){

        Stack<Node> stack = new Stack<>();

        stack.push(this.root);

        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(Objects.nonNull(cur.right)){
                stack.push(cur.right);
            }

            if(Objects.nonNull(cur.left)){
                stack.push(cur.left);
            }

        }
    }


    /**
     * 中序遍历
     */
    public void inOrder(){
        this.inOrder(this.root);
    }

    private void inOrder(Node node){

        if(Objects.isNull(node)){
            return;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);

    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        this.postOrder(this.root);
    }

    private void postOrder(Node node){

        if(Objects.isNull(node)){
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);


    }


    /**
     * 层序遍历
     * @Title: levelOrder
     * @Description:
     * @param
     * @return void
     * @modify
     * @throws
     * @author linzou@linkdoc.com
     * @date 2019/1/15 7:33 AM
     */
    public void levelOrder(){

        Queue<Node> nodeQueue = new LinkedList<>();

        nodeQueue.add(this.root);

        while(!nodeQueue.isEmpty()){
            Node cur = nodeQueue.remove();
            System.out.println(cur.e);

            if(Objects.nonNull(cur.left)){
                nodeQueue.add(cur.left);
            }

            if(Objects.nonNull(cur.right)){
                nodeQueue.add(cur.right);
            }
        }


    }


    /**
     * 查找二分搜索树中最小的元素
     * @return
     */
    public E minimum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }

        return minimum(this.root).e;
    }

    private Node minimum(Node node){

        if(Objects.isNull(node.left)){
            return node;
        }

        return minimum(node.left);
    }

    /**
     * 寻找二分搜索树最大的元素
     * @return
     */
    public E maximum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }

        return maximum(this.root).e;
    }

    private Node maximum(Node node){

        if(Objects.isNull(node.right)){
            return node;
        }

        return minimum(node.right);
    }

    /**
     *  删除最小节点
     * @return
     */
    public E removeMin(){
        E ret = minimum();
        //递归到最外层还是root
        this.root = removeMin(this.root);
        return ret;
    }

    private Node removeMin(Node node){

        if(Objects.isNull(node.left)){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 删除最大值
     * @return
     */
    public E removeMax(){
        E ret = maximum();
        this.root = removeMax(this.root);
        return ret;
    }

    private Node removeMax( Node node){

        if(Objects.isNull(node.right)){
            Node rightNode = node.left;
            node.left = null;
            size--;
            return rightNode;
        }

        node.right = removeMin(node.right);
        return node;

    }


    /**
     * 删除二分搜索树中的任意元素
     * @param e
     */
    public void remove(E e){
        root = remove(root,e);
    }

    private Node remove(Node node , E e ){

        if(Objects.isNull(node)){
            return null;
        }

        if(e.compareTo(node.e) < 0 ){
            node.left = remove(node.left,e);
            return node;
        }else if(e.compareTo(node.e) > 0){
            node.right = remove(node.right,e);
            return node;
        }else{

            if(Objects.isNull(node.left)){

                Node rightNode = node.right;
                node.right = null;
                size--;
                return  rightNode;

            }

            if(Objects.isNull(node.right)){

                Node leftNode = node.left;
                node.left = null;
                size--;
                return  leftNode;

            }

            Node successor = maximum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;

        }

    }



    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        generateBSTString(this.root,0,res);
        return res.toString();

    }


    private void generateBSTString(Node node,Integer depth,StringBuilder res){

        if(Objects.isNull(node)){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left,depth + 1 ,res);
        generateBSTString(node.right,depth + 1 ,res);
    }


    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for (int i=0;i<depth;i++){
            res.append("--");
        }
        return res.toString();
    }

}
